package ACWing.DataStructure.单调队列;
//154. 滑动窗口

import java.io.*;

/**
 * @author :chenjie
 * @date :Created 2022/12/28 17:44
 */
public class SlidingWindow {
    static int[]q=new int[1000010];
    static int[]a=new int[1000010];
    static int hh,tt;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
        String[] st = bf.readLine().split(" ");
        int m = Integer.parseInt(st[0]);
        int k = Integer.parseInt(st[1]);
        String[] str = bf.readLine().split(" ");
        for(int i = 0 ; i < m ; i ++ ) a[i] = Integer.parseInt(str[i]);

        hh=0;
        tt=-1;
        for (int i = 0; i < m; i++) {
            if(hh<=tt&&i-k+1>q[hh]){//个数超过k个了维持窗口数量
                hh++;
            }
            while (hh<=tt&&a[q[tt]]>=a[i]){//将比a【i】大的数删掉用下标数大而且值小的数的下标作为队头以此类推每次便可以看到最小数在队头
                tt--;
            }
            q[++tt]=i;
            if(i>=k-1){
                System.out.print(a[q[hh]]+" ");
            }

        }
        System.out.println();
        hh=0;
        tt=-1;
        for (int i = 0; i < m; i++) {
            if(hh<=tt&&i-k+1>q[hh]){//个数超过k个了
                hh++;
            }
            while (hh<=tt&&a[q[tt]]<=a[i]){
                tt--;
            }
            q[++tt]=i;
            if(i>=k-1){
                System.out.print(a[q[hh]]+" ");
            }

        }
    }
}
